#include<iostream>
#include<vector>
#include<unordered_map>
#include<string>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
	
};

class Solution {
private:
	string serilize(TreeNode *n, vector<TreeNode*>& res, unordered_map<string, int>& map) {
		if (n == NULL) return "#";
		string serial = to_string(n->val) + "," + serilize(n->left, res, map) + "," + serilize(n->right, res, map);
		if (map[serial]==1) {
			res.push_back(n);
		}
		map[serial]++;
		return serial;
	}

public:
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
		unordered_map<string, int> map;
		vector<TreeNode *> res;
		serilize(root, res, map);
		return res;
	}
};

void main() {
	TreeNode root(1), n2(2), n3(3), n4(4), n2l(2), n4l(4), n4r(4);
	root.left = &n2, root.right = &n3, n2.left = &n4, n3.left = &n2l, n3.right = &n4r, n2l.left = &n4l;
	Solution s;
	s.findDuplicateSubtrees(&root);
}